#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include "datrie.h"
#include "charset.h"
#include "mylog.h"

#define DICT_ITEM_CPY(d, s) do{ strncpy((d).word, (s).word, DICT_ITEM_LEN); (d).freq = (s).freq;}while(0)
#define DICT_ITEM_CMP(s1, s2) strncmp((s1).word, (s2).word, DICT_ITEM_LEN)

static const unsigned char utf8_mask[] = {0x1F, 0x7F, 0x7F};

#define EN_CHAR(s, i)	((char)(s)[(i)] & utf8_mask[(i)%3])

static int grow(dat * p)
{
	assert(p != NULL);
	if(p->_base + 256 < p->_volume){
		return 1;
	}
	unsigned int new_volume = ((p->_base + 256) / DAT_BLOCK_SIZE + 1) * DAT_BLOCK_SIZE;
	dat_node * new_da = (dat_node *)realloc( p->_da, new_volume * sizeof(struct dat_node));
	if(new_da == NULL){
#ifndef NDEBUG
		logit(LV_FATAL, "dat realloc %x", new_volume * sizeof(struct dat_node));
#endif
		return -1;
	}
	memset(new_da + p->_volume, 0, (new_volume - p->_volume) * sizeof(struct dat_node));
	p->_da = new_da;
	p->_volume = new_volume;
#ifndef NDEBUG
	logit(LV_DEBUG, "dat realloc [%p]%.1fM", p->_da, (float)(p->_volume * sizeof(struct dat_node)) / (1<<20));
#endif
	return 0;
}

dat * dat_new()
{
#ifndef NDEBUG
	logit(LV_LOG, "datrie new ...");
#endif
	dat * p = (dat *)malloc(sizeof(struct dat));
	if(p == NULL){
		return NULL;
	}
	memset(p, 0, sizeof(struct dat));
	return p;
}

int _dat_dump_init(dat * p)
{
	assert(p != NULL);
	p->_root = DAT_DEF_ROOT;
	p->_base = DAT_DEF_ROOT + 1;
	p->_dt = (dict_item *)malloc(sizeof(struct dict_item) * DICT_SIZE);
	if(p->_dt == NULL){
		return -1;
	}
	memset(p->_dt, 0, sizeof(struct dict_item) * DICT_SIZE);
	if(grow(p) < 0){
		free(p->_dt);
		return -2;
	}
	return 0;
}

int dat_free(dat * p)
{
	assert( p != NULL);
#ifndef NDEBUG
	logit(LV_LOG, "datrie free ...");
#endif
	free(p->_da);
	p->_da = NULL;
	p->_volume = 0;
	p->_root = 0;
	p->_base = 0;
	free(p->_dt);
	p->_dt = NULL;
	p->_dt_size = 0;
	free(p);
	return 0;
}

//1. if res == NULL, fetch until depth and return parent 
//2. if depth < 0 and res != NULL, fetch all result
int dat_fetch(const dat *p, const char * str, int depth, dat_res * res)
{
	if(p == NULL || str == NULL ){
		return -1;
	}
	int i = 0;
	unsigned char ch = '\0';
	int parent = p->_root;
	int base = p->_root + 1;

	if(depth < 0){
		depth = DICT_ITEM_LEN;
	}
	if(res != NULL){
		memset(res, 0, sizeof(struct dat_res));
	}

#define ISASCII(c)    (((c) & ~0x7f) == 0)
	for(i=0; i<depth; i++){
		if(ISASCII(str[i])){	//cant find english
			break;
		}
		ch = EN_CHAR(str, i);//encode utf8 to reduce space
		base = abs(p->_da[parent].base);
		if(p->_da[base+ch].base == 0 && p->_da[base+ch].check == 0){
#ifndef NDEBUG
			if(res == NULL) logit(LV_ERROR, "fetch: %s:%d[%x] prefix can't be found", str, i, (unsigned int)ch);
#endif
			break;
		}
		if(p->_da[base+ch].check != parent){
#ifndef NDEBUG
			if(res == NULL) logit(LV_ERROR, "fetch: %s:%d[%x] clue broken, check:%u, parent:%u", str, i, (unsigned int)ch, p->_da[base+ch].check, parent);
#endif
			break;
		}
		//is a termination, set res
		if(res != NULL && p->_da[base+ch].freq > 0){
			res->item[res->num].i = base+ch;
			res->item[res->num].len = i+1;
			res->item[res->num].freq = p->_da[base+ch].freq;
			res->item[res->num].tag = p->_da[base+ch].tag;
			assert(res->item[res->num].len > 0 && (res->item[res->num].tag & _z_));
			res->num ++;
			if(res->num == DAT_RES_MAX){
#ifndef NDEBUG
				logit(LV_ERROR, "fetch too more res");
#endif
				return -2;
			}
		}
		parent = base + ch;
	}
#undef ISASCII
	return parent;
}

static int _dat_insert(dat *p, int j, int depth)
{
	assert(p != NULL && j >= 0 && depth >= 0);
	dict_item *t = &(p->_dt[j]);
	unsigned char ch = t->word[depth];
	if(ch == '\0'){
#ifndef NDEBUG
		logit(LV_ERROR, "insert: %s, %d, mustn't be termination", t->word, depth);
#endif
		return -1;
	}
	ch = EN_CHAR(t->word, depth);
	int parent = dat_fetch(p, t->word, depth, NULL);
	if(parent < 0){
#ifndef NDEBUG
		logit(LV_ERROR, "parent too large\n");
#endif
		return -2;
	}
	if(p->_da[parent].base == 0){
		p->_da[parent].base = (p->_base - ch == 0)?1:(p->_base - ch);
	}
	int base = abs(p->_da[parent].base);
	if(p->_da[base+ch].base != 0 || p->_da[base+ch].check != 0){
		if(p->_da[base+ch].check != parent){
			return -3;
		}
		return 1;
	}
	p->_da[base+ch].base = 0;
	//if it's a termination, set freq 
	if(depth + 1 == t->len){
		if(p->_da[base+ch].freq != 0){
#ifndef NDEBUG
			logit(LV_ERROR, "insert: %s, %d has been inserted", t->word, depth);
#endif
			return -4;
		}
		p->_da[base+ch].freq = t->freq;
		p->_da[base+ch].tag = t->tag;
	}
	p->_da[base+ch].check = parent;
	p->_base = base + ch + 1;
	p->_size ++;
/*
 *assuming signed overflow does not occur when assuming that (X + c) < X is always false
	if(p->_base + 256 < p->_base){
#ifndef NDEBUG
			logit(LV_ERROR, "base to large %d", p->_base);
#endif
		return -5;
	}
*/
	if(p->_base + 256 > p->_volume && grow(p) < 0){
		return -6;
	}
	return 0;
}
/*
static int partition(dict_item *p, int size)
{
	assert(p != NULL);
	dict_item pivot;
	memcpy(&pivot, &p[0], sizeof(struct dict_item));
	int high = size - 1;
	int low = 0;

	if(size < 2){
		return 0;
	}
	
	while(low != high){
		while(low < high){
			if(strncmp(p[high].word, pivot.word, DICT_ITEM_LEN) < 0){
				memcpy(&p[low++], &p[high], sizeof(struct dict_item));
				break;
			}
			high --;
		}
		while(low < high){
			if(strncmp(p[low].word, pivot.word, DICT_ITEM_LEN) > 0){
				memcpy(&p[high--], &p[low], sizeof(struct dict_item));
				break;
			}
			low ++;
		}
	}
	//low == high
	memcpy(&p[low], &pivot, sizeof(struct dict_item));
	return low;
}

static int quick_sort(dict_item *p, int size)
{
	assert(p != NULL);
	if(size < 2){
		return 0;
	}
	int pos = partition(p, size);
	quick_sort(p, pos);
	quick_sort(p+pos+1, size-pos-1);
	return 0;
}
*/
static int check_order(dict_item *p, int size)
{
	assert(p != NULL);
	if(size < 2){
		return 0;
	}
	int i = 0;
	for(i=0; i<size-1; i++){
		if(strncmp((p + i)->word, (p + i+1)->word, DICT_ITEM_LEN) > 0){
#ifndef NDEBUG
			logit(LV_ERROR, "wrong order while cmp line %d with %d", i+1, i+2);
#endif
			return -1;
		}
	}
	return 0;
}

static int _dat_build(dat *p)
{
	assert(p != NULL && p->_dt != NULL && p->_dt_size >= 0);
	if(p->_dt_size == 0){
		return 1;
	}

//	quick_sort(p->_dt, p->_dt_size);
	if(check_order(p->_dt, p->_dt_size) < 0){
		fprintf(stderr, "check order failed\n");
		return -1;
	}

	int i = 0;
	int j = 0;
	int flag = 0;
	//each time process one byte
	//make index 1 to be root and base is 2
	for(i=0; i<DICT_ITEM_LEN; i++){
		flag = 0;
		for(j=0; j<p->_dt_size; j++){
			if(i >= (p->_dt+j)->len){
				continue;
			}
			if(_dat_insert(p, j, i) < 0){
				return -2;
			}
			flag ++;
		}
		if(flag == 0){
			break;
		}
	}
#ifndef NDEBUG
	logit(LV_LOG, "build: size/base/volume: %d/%d/%d", p->_size, p->_base, p->_volume);
#endif
	return p->_size;
}


//trim the blank at begin or end
static char * trim(char * str)
{
	assert(str != NULL);
	int i = 0;
	int len = strlen(str);
	if(len == 0){
		return NULL;
	}
	for(i=len-1; i>=0; i--){
		if(str[i] == '\t' || str[i] == ' '){
			continue;
		}
		break;
	}
	str[i+1] = '\0';
	len = strlen(str);
	int j = 0;
	for(i=j=0; i<len; i++){
		if((str[i] == '\t' || str[i] == ' ') && j == 0){
			continue;
		}
		if(j != i){
			str[j] = str[i];
		}
		j++;
	}
	str[j] = '\0';
	return str;
}

static int check_cjk(char *str)
{
	assert(str != NULL);
	int i = 0;
	int len = strlen(str);
	for(i=0; i<len; i++){
		if((str[i] & (~utf8_mask[i%3])) != ~utf8_mask[i%3]){
			return -1;
		}
	}
	return 0;
}

int dat_load(dat * p, const char * dat_path)
{
	if(p == NULL || dat_path == NULL){
		return -1;
	}
	FILE *datfp = fopen(dat_path, "r");
	if(datfp == NULL){
		return -2;
	}
	p->_root = DAT_DEF_ROOT;
	if(fread(&p->_size, sizeof(int), 1, datfp) != 1){
		return -3;
	}
	if(p->_size < 0){
#ifndef NDEBUG
	logit(LV_ERROR, "load size %d", p->_size);
#endif
		return -4;
	}
	p->_base = p->_size + 1;
	p->_volume = 0;
	if(grow(p) < 0){
		return -5;
	}
	if(fread(p->_da, sizeof(struct dat_node), p->_size, datfp) != p->_size){
		return -6;
	}
	fclose(datfp);
	return 0;
}
	
int dat_dump(dat * p, const char * dict_path, const char * dat_path)
{
	if(p == NULL || dict_path == NULL || dat_path == NULL){
		return -1;
	}
	FILE *dictfp = fopen(dict_path, "r");
	if(dictfp == NULL){
		return -2;
	}
	FILE *datfp = fopen(dat_path, "w+");
	if(datfp == NULL){
		return -3;
	}
	if(_dat_dump_init(p) < 0){
		return -4;
	}
	dict_item * t = p->_dt;
	int i = 0;
	char * s = NULL;
	char * s1 = NULL;
	while(fgets(t->word, DICT_ITEM_LEN, dictfp) && i++ < DICT_SIZE){
		if((s=strstr(t->word, "\n")) == NULL){
#ifndef NDEBUG
			logit(LV_ERROR, "word %s is longer than %u, line %u", t->word, DICT_ITEM_LEN, i);
#endif
			continue;
		}
		*s = '\0';
		if((s=strstr(t->word, "\t")) == NULL){
#ifndef NDEBUG
			logit(LV_ERROR, "word %s with no tab, line %u", t->word, i);
#endif
			continue;
		}
		*s = '\0';
		if(s - t->word <= 0 || s - t->word > DICT_ITEM_LEN - 1){
#ifndef NDEBUG
			logit(LV_ERROR, "word %s is empty, line %u", t->word, i);
#endif
			continue;
		}
/*
		if((s1=strstr(s+1, "\t")) != NULL){
			*s1 = '\0';
			t->tag = atol(s1+1);
			if(strcmp(t->word, "奥") == 0){
				fprintf(stderr, "%s, %s->%d\n", t->word, s1+1, t->tag);
			}
		}
		t->tag |= _z_;
		t->len = s - t->word;
		t->freq = atol(s+1)==0?1:atol(s+1);
*/
		t->len = s - t->word;
		t->freq = strtoul(s+1, &s1, 16);
		if(t->freq == 0){
#ifndef NDEBUG
			logit(LV_ERROR, "%s %s, freq is 0, line %u", t->word, s+1, i);
#endif
			t->freq = 1;
		}
		if(*s1 != '\0'){
			t->tag = strtoul(s1+1, NULL, 16);
		}
		t->tag |= _z_;
		trim(t->word);
		if(check_cjk(t->word) < 0){
#ifndef NDEBUG
			logit(LV_ERROR, "word %s is not cjk, line %u", t->word, i);
#endif
			continue;
		}
		
		t ++;
	}
	if(i >= DICT_SIZE){
#ifndef NDEBUG
		logit(LV_ERROR, "words is more than %u", DICT_SIZE);
#endif
		return -5;
	}
	p->_dt_size = i;
	if(_dat_build(p) < 0){
		return -6;
	}
	if(fwrite(&p->_base, sizeof(int), 1, datfp) < 0){
		return -7;
	}
	if(fwrite(p->_da, sizeof(struct dat_node), p->_base, datfp) < 0){
		return -8;
	}

	fclose(dictfp);
	fclose(datfp);
	return 0;
}

#ifdef DATRIE_MAIN
int main(int argc, char ** argv)
{
	logon();
	dat * p = dat_new();
	int ret = dat_dump(p, "/home/aaron/workspace/hiseg/dict/hidict.utf8", "/home/aaron/workspace/hiseg/dict/hidict.dat");
	if(ret < 0){
		printf("dump err, %d\n", ret);
		return 1;
	}
	dat_free(p);
	p = dat_new();
	ret = dat_load(p, "/home/aaron/workspace/hiseg/dict/hidict.dat");
	if( ret < 0){
		printf("load dict, ret=%d\n", ret);
		return 1;
	}

	dat_res res;
	ret = dat_fetch(p, "乡", -1, &res);
	if( ret < 0){
		printf("fetch, ret=%d\n", ret);
		return 2;
	}
	printf("res: %d\n", res.num);
	int i = 0;
	for(i = 0; i<res.num; i++){
		printf("r%d: %d, %x, %x\n", i, res.item[i].len, res.item[i].freq, res.item[i].tag);
	}

	dat_free(p);
	logoff();

	return 0;
}
#endif
